package com.desin.modle.datastruct.algo.backtrackingAlgorithm.zeroOnePackage;

import java.util.Arrays;

public class Solution {
    public int maxWigeht = Integer.MIN_VALUE;

    public int maxValue = Integer.MIN_VALUE;

    public boolean[][] flag = new boolean[5][100];

    public void f(int i,int cw,int[] items,int n,int w){
        if(cw==w||i==n){
            if(cw>maxWigeht){
                maxWigeht = cw;
            }
            return;
        }
        f(i+1,cw,items,n,w);
        if(cw+items[i]<=w){
            f(i+1,cw+items[i],items,n,w);
        }
    }

    public void test(int index,int currentWeight,int[] items,int maxNum,int limitWeight){
        if(index==maxNum||currentWeight>=limitWeight){
            if(currentWeight>maxWigeht){
                maxWigeht=currentWeight;
            }
            return;
        }
        if(flag[index][currentWeight]){
            return;
        }
        flag[index][currentWeight]=true;
        test(index+1,currentWeight,items,maxNum,limitWeight);
        if(currentWeight+items[index]<=limitWeight){
            test(index+1,currentWeight+items[index],items,maxNum,limitWeight);
        }
    }

    public void test1(int index,int cw,int cv,int[] items,int[] values,int maxNum,int limitWeight){
        if(index==maxNum||cw>=limitWeight){
            if(cw>maxWigeht){
                maxWigeht=cw;
            }
            if(cv>=maxValue){
                maxValue=cv;
            }
            return;
        }
        if(flag[index][cw]){
            return;
        }
        flag[index][cw]=true;
        test1(index+1,cw,cv,items,values,maxNum,limitWeight);
        if(cw+items[index]<=limitWeight){
            test1(index+1,cw+items[index],cv+values[index],items,values,maxNum,limitWeight);
        }
    }
    int count =0;
    public int findTarget(int[] nums,int target){
        findTargetHelper(nums,0,0,target);
        return count;
    }

    public void findTargetHelper(int[] nums,int index,int sum,int target){
        if(index==nums.length){
            if(sum==target){
                count++;
            }
            return;
        }
        findTargetHelper(nums,index+1,sum+nums[index],target);
        findTargetHelper(nums,index+1,sum-nums[index],target);
    }

    public void manjian(int[] prices,int condition){
        int num = prices.length;
        int max = condition*3;
        boolean[][] status = new boolean[num][max+1];
        status[0][0]=true;
        status[0][prices[0]]=true;
        for(int i=1;i<num;i++){
            for(int j=0;j<=max;j++){
                if(status[i-1][j]){
                    status[i][j]=true;
                }
            }
            for(int j=0;j<=max-prices[i];j++){
                if(status[i-1][j]){
                    status[i][j+prices[i]]=true;
                }
            }
        }
        int minValue = -1;
        for(int begin=condition;begin<=max;begin++){
            if(status[num-1][begin]){
                minValue=begin;
                break;
            }
        }
        for(int i=num-1;i>=1;i--){
            if(minValue-prices[i]>=0&&status[i-1][minValue-prices[i]]){
                System.err.println();
                minValue=minValue-prices[i];
            }
        }
        if(minValue>=0){

        }
    }

    public int erwei(int[][] data){
        int[][] remark = new int[data.length][data[0].length];
        return erweiHelper(data.length-1,data[0].length-1,data,remark);
    }

    private int erweiHelper(int i, int j, int[][] data, int[][] remark) {
        if(i==0&&j==0){
            return data[0][0];
        }
        if(remark[i][j]>0){
            return remark[i][j];
        }
        int downValue = Integer.MAX_VALUE;
        if(i-1>=0){
            downValue = erweiHelper(i-1,j,data,remark);
        }
        int rightValue = Integer.MAX_VALUE;
        if(j-1>=0){
            rightValue=erweiHelper(i,j-1,data,remark);
        }
        int currentValue = data[i][j]+Math.min(downValue,rightValue);
        remark[i][j]=currentValue;
        return currentValue;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int erwei = solution.erwei(new int[][]{{1, 2, 4}, {2, 3, 7}, {7, 4, 2}, {3, 7, 1}});
        System.err.println(erwei);
    }

    public int erweiNew(int[][] data){
        int row = data.length;
        int colum = data[0].length;
        int[][] status = new int[row][colum];
        for(int i=0;i<row;i++){
            for(int j=0;j<colum;j++){
                status[i][j]=-1;
            }
        }
        int sum = 0;
        for(int i=0;i<row;i++){
            status[i][0]=sum+data[i][0];
        }
        sum =0;
        for(int i=0;i<colum;i++){
            status[0][i]=sum+data[0][i];
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<colum;j++){
                status[i][j]=data[i][j]+Math.min(status[i-1][j],status[i][j-1]);
            }
        }
        return status[row-1][colum-1];
    }

}
